package twobranchsearch.kthlargest;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Date 2020/03/13
 * @author 王光浩
 * @Thinking 使用暴力法解决。每次加入数据我们都需要重新将数组进行排序。
 * @Analysis 时间复杂度O（n^2），空间复杂度O（k）。
 */
public class MyMethodOne {
		private ArrayList<Integer> sort;     //保存前k个数据
		private int th;
		public MyMethodOne(int k, int[] nums) {
			sort=new ArrayList<Integer>();
			Arrays.sort(nums);
			th=k;
			//将前k个数据保存在在sort中（按照降序排列）
			if(nums.length>0) {
				int index=nums.length-1;
				while(sort.size()<k && index>=0) {
					sort.add(nums[index--]);
				}
			}
	    }
	    /*
	     * @向数组中添加数据，并且返回第k大的数据
	     */
	    public int add(int val) {
	    	for(int i=0;i<sort.size();i++) {
	    		if(sort.get(i)<=val) {
	    			sort.add(i,val);
	    			break;
	    		}
	    	}
	    	if(sort.size()<th)
	    		sort.add(val);
    		if(sort.size()>th)
        		sort.remove(sort.size()-1);
	    	return sort.get(sort.size()-1);
	    }
}
